home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / BBS-Archive / Dev / GNU-SMALLTALK.lha / LinkedList.st < prev    next >
Text File  |  1992-02-15  |  4KB  |  155 lines
  1. "======================================================================
  2. |
  3. |   LinkedList Method Definitions
  4. |
  5.  ======================================================================"
  6.  
  7.  
  8. "======================================================================
  9. |
  10. | Copyright (C) 1990, 1991, 1992 Free Software Foundation, Inc.
  11. | Written by Steve Byrne.
  12. |
  13. | This file is part of GNU Smalltalk.
  14. |
  15. | GNU Smalltalk is free software; you can redistribute it and/or modify it
  16. | under the terms of the GNU General Public License as published by the Free
  17. | Software Foundation; either version 1, or (at your option) any later version.
  18. | 
  19. | GNU Smalltalk is distributed in the hope that it will be useful, but WITHOUT
  20. | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  21. | FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  22. | details.
  23. | 
  24. | You should have received a copy of the GNU General Public License along with
  25. | GNU Smalltalk; see the file COPYING.  If not, write to the Free Software
  26. | Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  
  27. |
  28.  ======================================================================"
  29.  
  30.  
  31. "
  32. |     Change Log
  33. | ============================================================================
  34. | Author       Date       Change 
  35. | sbb         16 Mar 91      Class creation now separate statement.
  36. |
  37. | sbb         21 Sep 90      Removed printOn: method; the one from Collection
  38. |              should be ok.  Also, the storeOn: method from
  39. |              Collection should be ok.
  40. |
  41. | sbyrne     25 Apr 89      created.
  42. |
  43. "
  44.  
  45. SequenceableCollection subclass: #LinkedList
  46.                instanceVariableNames: 'firstLink lastLink'
  47.                classVariableNames: ''
  48.                poolDictionaries: ''
  49.                category: nil
  50. !
  51.  
  52. LinkedList comment:
  53. 'I provide methods that access and manipulate linked lists.  I assume that 
  54. the elements of the linked list are subclasses of Link, because I use 
  55. the methods that class Link supplies to implement my methods.' !
  56.  
  57. !LinkedList methodsFor: 'accessing'!
  58.  
  59. at: index
  60.     "Return the element that is index into the linked list."
  61.     | i element |
  62.     i _ 1.
  63.     element _ firstLink.
  64.     [element isNil] whileFalse:
  65.         [ i = index ifTrue: [ ^element ].
  66.       i _ i + 1.
  67.       element _ element nextLink ].
  68.     ^self error: 'index out of bounds in linked list'
  69. !
  70.  
  71. at: index put: object
  72.     self error: 'Do not store into a LinkedList using at:put:'
  73. !!
  74.  
  75.  
  76.  
  77. !LinkedList methodsFor: 'adding'!
  78.  
  79. add: aLink
  80.     "Add aLink at the end of the list; return aLink."
  81.     self addLast: aLink.
  82.     ^aLink
  83. !
  84.  
  85. addFirst: aLink
  86.     "Add aLink at the head of the list; return aLink."
  87.     lastLink isNil ifTrue: [ lastLink _ aLink ].
  88.     aLink nextLink: firstLink.
  89.     firstLink _ aLink.
  90.     ^aLink
  91. !
  92.  
  93. addLast: aLink
  94.     "Add aLink at then end of the list; return aLink."
  95.     firstLink isNil ifTrue: [ firstLink _ aLink ].
  96.     lastLink notNil ifTrue: [ lastLink nextLink: aLink ].
  97.     lastLink _ aLink.
  98.     ^aLink
  99. !
  100.  
  101. removeFirst
  102.     "Remove the first element from the list and return it, or error if the
  103.     list is empty."
  104.  
  105.     ^self remove: firstLink
  106.           ifAbsent: [ ^self error: 'attempted to remove from an empty list' ]
  107. !    
  108.  
  109. removeLast
  110.     "Remove the final element from the list and return it, or error if the
  111.     list is empty."
  112.  
  113.     ^self remove: lastLink
  114.           ifAbsent: [ ^self error: 'attempted to remove from an empty list' ]
  115. !
  116.  
  117. remove: aLink ifAbsent: aBlock
  118.     "Remove aLink from the list and return it, or invoke aBlock if it's not
  119.     found in the list."
  120.     | temp |
  121.     aLink == firstLink
  122.         ifTrue: [ firstLink _ firstLink nextLink.
  123.               firstLink isNil ifTrue: [ lastLink _ nil ] ]
  124.     ifFalse: [ temp _ firstLink.
  125.                [ temp isNil ifTrue: [ ^aBlock value ].
  126.              temp nextLink == aLink ] whileFalse:
  127.                  [ temp _ temp nextLink ].
  128.            temp nextLink: aLink nextLink.
  129.            aLink == lastLink ifTrue: [ lastLink _ temp ] ].
  130.     aLink nextLink: nil.
  131.     ^aLink
  132. !!
  133.  
  134.  
  135.  
  136. !LinkedList methodsFor: 'enumerating'!
  137.  
  138. do: aBlock
  139.     | aLink |
  140.     aLink _ firstLink.
  141.     [ aLink notNil] whileTrue:
  142.         [ aBlock value: aLink.
  143.       aLink _ aLink nextLink]
  144. !!
  145.  
  146.  
  147.  
  148. !LinkedList methodsFor: 'testing'!
  149.  
  150. isEmpty
  151.     "Returns true if the list contains no members"
  152.     ^firstLink isNil
  153. !!
  154.  
  155.